1. Field of the Invention
The present invention relates to a buffer storage which performs replacement processing based on an LRU (Least Recently Used) system and, more particularly, to an error processing system for a buffer storage which permits determination of a replace block even if an error occurs in an LRU circuit.
2. Description of the Prior Art
The LRU system replaces the least recently used data giving it first priority when moving out to a main storage data read out therefrom and stored in a buffer storage, so that data of the highest frequency use can be held in with buffer storage at all times.
In the buffer storage employing such an LRU system, a unit of data or a block to be replaced is usually determined in the following manner: An LRU circuit outputs an LRU pattern, that is information for determining the block to be replaced, and a replace logic circuit decodes each bit of the LRU information on the basis of a predetermined replacement algorithm and yields an output designating only one block to be replaced. On the other hand, an update logic circuit determines the order in which blocks were used, thereby updating the LRU pattern in the LRU circuit to ensure that the LRU pattern always holds information on the block to be replaced. This is based on the assumption that the most previously used or earliest used block would be the least recently used one, so that data having the highest frequency of use can always be loaded in the buffer storage.
In the case where a fixed or intermittent fault occurs in the LRU circuit and generates an LRU pattern other than a predetermined one, the replacement algorithm in the replace logic circuit is affected by the fault in the LRU circuit, resulting in no output being produced by the replace logic circuit for designating the block to be replaced because of the fault pattern. Such an error is a serious fault in the buffer storage for a swap system in which the update of data in the main storage is carried out only for the data loaded into the buffer storage. The reason is that in the swap system the opportunity for the data of the main storage to be updated is lost by the above-described error, in contrast to a store through system in which the same data loaded in the buffer storage and the main storage are simultaneously updated.
As a solution to this problem, duplication of the LRU circuit has been considered; however, this prevents the failure of the system but increases the amount of hardware used, resulting in increased manufacturing costs.